package offer;

public class Fib {
    static final int MOD = 1000000007;

    public static void main(String[] args) {
        System.out.println(fib(45));
        System.out.println(recursion(45));
    }

    public static int fib(int n) {

        if (n == 0 || n == 1) {
            return n;
        }

        int n1 = 0;
        int n2 = 1;
        int curr = 0;
        for (int i = 2; i <= n; i++) {
            curr = (n1 + n2) % MOD;
            n1 = n2;
            n2 = curr;
        }
        return curr;
    }


    private static int recursion(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        int res = (recursion(n - 1) + recursion(n - 2)) % MOD;
        return res;
    }

}

